/**
 * Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"
 */
package com.xinpan.exercise;

import java.util.ArrayList;

public class GenerateParenthesis {
    public ArrayList<String> generateParenthesis(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> res = new ArrayList<String>();
        if(n == 0)
            return res;
        
        generate(res, "(", n-1, 1);
        return res;
    }
    
    public void generate(ArrayList<String> res, String str, int left, int used)
    {
        if(left == 0)
        {
            while(used-- > 0)
                str += ")";
            res.add(str);
            return;
        }
        
        
        if(used > 0)
            generate(res, str + ")", left, used-1);
        generate(res, new String(str) + "(", left-1, used+1);
        
        return;
    }
}
